Definition (decision problem)

Consider the problem of finding a maximum sized independent set (set of vertices without any common edges) in a graph. The corresponding language is

𝙸𝙽𝙳𝚂𝙴𝚃={⟨G,k⟩:∃S⊆V(G) s.t. |S|≥k and ∀u,v∈S,uv∉E(G)}\mathtt{INDSET} = \{\langle G,k\rangle : \exists S \subseteq V(G) \text{ s.t. } \lvert S \rvert \geq k \text{ and } \forall u, v \in S, \overline{uv} \notin E(G)\}

Algorithm to solve this language will tell, on inputting graph GG and number kk, where there exists an independent set of size at least kk.

Notes

  • 𝙸𝙽𝙳𝚂𝙴𝚃∈\mathtt{INDSET} \in NP
    • in fact, 𝙸𝙽𝙳𝚂𝙴𝚃∈\mathtt{INDSET} \in NP-C

References

  1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, pp. 3, 39.
  2. https://web.stanford.edu/class/archive/cs/cs103/cs103.1142/lectures/28/Small28.pdf
  3. https://people.engr.tamu.edu/andreas-klappenecker/csce658-s18/complexity.pdf